import unittest
class Node():
    def __init__(self,val):
        self.data=val
    
    def __repr__(self):
        return 'data:'+str(self.data)


class Stack():
    def __init__(self):
        self.buf=[]
    def push(self,val):
        self.buf.append(Node(val))
    def pop(self):
        if self.buf:
            return self.buf.pop(-1).data
        return None
    def size(self):
        return len(self.buf)
    def peek(self):
        if self.buf:
            return self.buf[-1].data
        return None
    def isEmpty(self):
        return not self.buf
    
class MinStack():
    def __init__(self):
        self.buf=[]
    def push(self,val):
        newNode = Node(val)
        if self.buf and self.buf[-1].min<val:
                newNode.min=self.buf[-1].min
        else:
            newNode.min=val 
        self.buf.append(newNode)
    def pop(self):
        if self.buf:
            return self.buf.pop(-1).data
        return None
    def min(self):
        if self.buf:
            return self.buf[-1].min    
    
    
class TestMinStack(unittest.TestCase):
    inputs = (([1,2,3,1,5],1,1),
              ([1,2,0,1,5],0,0),
              ([1,2,3,1,10,0],0,1),
              ([1],1,None),
              ([],None,None),
              )
    def testMin(self):
        for li,m1,m2 in self.inputs:
            stack = MinStack()
            for it in li:
                stack.push(it)
            self.assertEqual(stack.min(),m1)
            stack.pop()
            self.assertEqual(stack.min(),m2)
            
            
class SetOfStacks():
    def __init__(self):
        self.stacks=[]
        self.size=0
        self.limit=5
        self.stacks.append(Stack())
    
    def push(self,val):
        if self.stacks[self.size].size()==self.limit:
            self.stacks.append(Stack())
            self.size+=1
        self.stacks[self.size].push(val)
        
    def pop(self):
        if self.stacks[self.size].size()==0 and self.size>0:
            self.stacks.pop()
            self.size-=1
        return self.stacks[self.size].pop()
    
class TestSetOfStacks(unittest.TestCase):
    inputs = (
             ([1,2,3,4,5,6,7],[7,6,5],[1,2,3],[3,2,1]),
             ([1,2,3,4,5,6,7],[7,6,5],[1,2,3],[3,2,1,4,3,2,1,None]),
             )
    def testInputs(self):
        for input in self.inputs:
            superSt = SetOfStacks()
            #cada input tem varias listas, que sao push ou checadas com pop alternadamente
            toPop=False
            for inp in input:
                for el in inp:
                    if toPop:
                        self.assertEqual(superSt.pop(), el)
                    else:
                        superSt.push(el)
                toPop=not toPop
                
                
def hanoi(n,orig,aux,dest):
    "3.4"
    #TODO: fazer sem ser recursivo
    if n==1:
        print 'move %d from %s to %s'%(n,orig,dest)
        return
    hanoi(n-1,orig,dest,aux)
    print 'move '+str(n)+' from %s to %s '%(orig,dest)
    hanoi(n-1,aux,orig,dest)
                        
class MyQueue():
    "3.5"
    def __init__(self):
        self.st1=Stack()    
        self.st2=Stack()
        self.pos = 0
    
    def enqueue(self,val):
        self.st1.push(val)
    
    def dequeue(self):
        if self.st2.size()==0:
            while self.st1.size()>0:
                self.st2.push(self.st1.pop())
        return self.st2.pop()
        

                
    
class TestMyQueue(unittest.TestCase):
    inputs = (
             ([1,2,3,4,5,6,7],[1,2,3],[1,2,3],[4,5,6,7,1,2,3,None],[1,2,3],[1,2,3]),
             ([],[None],[1,2],[1,2]),
             )
    def testInputs(self):
        for input in self.inputs:
            superSt = MyQueue()
            #cada input tem varias listas, que sao push ou checadas com pop alternadamente
            toPop=False
            for inp in input:
                for el in inp:
                    if toPop:
                        self.assertEqual(superSt.dequeue(), el)
                    else:
                        superSt.enqueue(el)
                toPop=not toPop
                
                
def sortStack(st):
    "3.6"
    sst=Stack()
    while not st.isEmpty():
        tmp=st.pop()
        while sst.peek()>tmp:
            st.push(sst.pop())
        sst.push(tmp)
    print sst.buf
    return sst
    

class TestSortStack(unittest.TestCase):
    inputs =(([5,4,3,2,1],[1,2,3,4,5]),
             ([5,2,3,4,1],[1,2,3,4,5]),
             )
    def testSort(self):
        for li,res in self.inputs:
            testSt = Stack()
            for it in li:
                testSt.push(it)
            rss = sortStack(testSt)
            for it in xrange(1,len(res)+1):
                self.assertEqual(rss.pop(),res[len(res)-it])
        
        
                
        
        

    